package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-08-24
 **/

public class No787K站中转内最便宜的航班 {

    /**
     * 有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
     * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，
     * 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
     *  
     *
     * 示例 1：
     * 输入:
     * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     * src = 0, dst = 2, k = 1
     * 输出: 200
     * 解释:
     * 城市航班图如下
     *
     * 从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
     * 示例 2：
     *
     * 输入:
     * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     * src = 0, dst = 2, k = 0
     * 输出: 500
     * 解释:
     * 城市航班图如下
     *
     * 从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
     *  
     *
     * 提示：
     * 1 <= n <= 100
     * 0 <= flights.length <= (n * (n - 1) / 2)
     * flights[i].length == 3
     * 0 <= fromi, toi < n
     * fromi != toi
     * 1 <= pricei <= 104
     * 航班没有重复，且不存在自环
     * 0 <= src, dst, k < n
     * src != dst
     */

    private int[][] arr;

    /**
     * f(count,city)=minPrice  从起点走count次到city的最少花费
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {

        arr = new int[k + 2][n];

        int maxPrice = (k + 1) * 10000;
        for (int[] ints : arr) {
            Arrays.fill(ints, maxPrice);
        }

        // 起点花费为0
        arr[0][src] = 0;

        k++;
        // 次数
        for (int i = 1; i <= k; i++) {

            // 城市
            for (int[] flight : flights) {
                int city = flight[0];
                int target = flight[1];
                int price = flight[2];
                arr[i][target] = Math.min(arr[i][target], arr[i-1][city] + price);
            }

        }

        int result =Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            result = Math.min(result, arr[i][dst]);
        }

        return result == maxPrice ? -1 : result;
    }

    public static void main(String[] args) {
        No787K站中转内最便宜的航班 n = new No787K站中转内最便宜的航班();
        int[][] arr = {{4,1,1},{1,2,3},{0,3,2},{0,4,10},{3,1,1},{1,4,3}};
        int result = n.findCheapestPrice(5, arr, 2, 1, 1);
        System.out.println(result);
    }

}
